package 力扣;

import java.util.ArrayList;
import java.util.List;

public class 将数组拆分成斐波那契数列 {
    public static void main(String[] args) {
        String S="123";
        List<Integer> list = splitIntoFibonacci(S);
        System.out.println(list.toString());
    }
    public static List<Integer> splitIntoFibonacci(String S) {
         List<Integer> res = new ArrayList<>();
         return dfs(S,0,res)?res:new ArrayList<Integer>();
    }
    private static boolean dfs(String S, int start, List<Integer> res) {
        int len=S.length();
        int p=res.size();
        if (start==len)
            return p>2;
        int num=0;
        for (int i = start; i <len ; i++) {
             num=num*10+S.charAt(i)-'0';
             if (num<0)
                 return false;
             if (p<2 || res.get(p-2)+res.get(p-1)==num) {
                 res.add(num);
                 if (dfs(S,i+1,res))
                     return true;
                 res.remove(p);
             }
             if (S.charAt(i)-'0'==0 && i==start)
                 return false;
        }
        return false;
    }
}
